点亮战争迷雾[200分]

题目内容

有一张二叉树地图，每一个节点都被战争迷雾所覆盖。在二叉树节点上插上一个侦察守卫，可以照亮该节点自身以及它的父节点和它的子节点的战争迷雾。在每个节点上插上侦察守卫的成本并不一样，用 $cost[i]$ 表示节点 $i$ 上的成本，每个节点的成本是正整数。

要求：

• 所有的战争迷雾都被驱散。
• 所花费的总成本最小。

补充说明：

• 单个节点的成本，$1 \le cost[i] \le 100$；
• 节点总数量 $\le 1000$。

输入描述

一行，一个层序遍历字符串（含首尾圆括号），空节点用 # 表示，例如 (5,1,10,2,8,#,3)。

输出描述

输出最小的总费用。

样例

样例 1

输入

5,1,10,2,8,#,3

输出

4

说明：

树结构图：

              1(5)
            /   \
           2(1)  3(10)
          / \     \
         4(2) 5(8) 6(3)

最优方案：在节点 2（成本 1）和节点 6（成本 3）插上侦察守卫，总成本 4。节点 2 覆盖 2,1,4,5；节点 6 覆盖 6,3；所有节点均被覆盖。

样例 2

输入

3,1,1

输出

2

说明：

树结构：

             1(3)
            /   \
           2(1)  3(1)

方案一：在节点 1 插上侦察守卫，可照亮所有地图，成本是 3。方案二：在节点 2 和节点 3 插上侦察守卫，可照亮所有地图，成本是 $1+1=2$。因此，最低成本的方案是方案二，返回值是 2。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (input) => {
    const arr = input.split(',').map(v => {
        if (v !== '#') {
            return Number(v); 
        } else {
            return '#';
        }
    })
    function buildTree() {
        const root = {cost: arr[0], left: null, right: null};
        let i=1;
        let queue = [root];
        while(queue.length && i<arr.length) {
            let node = queue.shift();
            if (i<arr.length && arr[i] !== '#') {
                node.left = {cost: arr[i], left: null, right: null}
                queue.push(node.left);
            }
            i++;
            if (i<arr.length && arr[i] !== '#') {
                node.right = {cost: arr[i], left: null, right: null}
                queue.push(node.right);
            }
            i++;
        }
        return root;
    }
    const root = buildTree();
    // dp0 自己亮+儿子最小成本+父亲最小成本
    // dp1 自己被儿子照亮。左儿子一定亮+右儿子。左儿子+右儿子一定亮
    // dp2 自己被父亲照亮。左儿子父亲不亮+右儿子父亲不亮
    const dfs = (node) => {
        if (!node) return [Infinity, 0, 0]; //我不能买灯（太贵了选不上我），但我不需要被照（免费），我不需要等爹照（免费）
        const [cost1, l1, l2] = dfs(node.left);
        const [cost2, r1, r2] = dfs(node.right);
        const self = node.cost + Math.min(cost1, l1, l2) + Math.min(cost2, r1, r2);
        const dad = Math.min(cost1, l1) + Math.min(cost2, r1);// 儿子不是被父亲照亮
        const left = cost1 + Math.min(cost2, r1);// 左儿子一定亮+右儿子不被父亲照亮（自己没亮）
        const right = cost2 + Math.min(cost1, l1);
        const son = Math.min(left, right);
        return [self, son, dad];
    }
    const [dp0, dp1, dp2] = dfs(root);
    console.log(Math.min(dp0, dp1));
    
})